package com.test.sort;

import java.util.Arrays;
import java.util.Objects;

/**
 * 快速
 * @author sujiafa
 * @date 2024/8/16
 */
public class QuickSort {

    public int[] sortArray(int[] nums) {
        if (Objects.isNull(nums) || nums.length == 0) {
            return nums;
        }

        quickSort(nums, 0, nums.length - 1);

        return nums;
    }

    public void quickSort(int[] nums, int low, int high) {

        if (low > high) {
            return;
        }

        // 基准位
        int pivot = nums[low];
        int i = low;
        int j = high;

        while (i < j) {

            // 先看右边
            while (i < j && nums[j] >= pivot) {
                j--;
            }

            // 再看左边
            while (i < j && nums[i] <= pivot) {
                i++;
            }

            // 交换
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }

        // 最后将基准为与i和j相等位置的数字交换
        nums[low] = nums[i];
        nums[i] = pivot;

        quickSort(nums, low, i - 1);
        quickSort(nums, i + 1, high);
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        System.out.println(Arrays.toString(quickSort.sortArray(new int[]{110, 100, 0})));
    }
}
